package com.adee.algorithm.structure;

// 跳表，参考 https://blog.csdn.net/weixin_45480785/article/details/116293416
/**
 * 跳表使用类似二分法数据结构，利用节点数据冗余，空间换时间，实现快速增删查
 *
 */

import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.concurrent.ThreadLocalRandom;

public class SkipList {
    private final int MAX_LEVEL = 16;
    private int topLevelIndex = 0;
    private Node[] head;

    public static void main(String[] args) {
        SkipList skipList = new SkipList();
        Node node1 = skipList.find(0);
        System.out.println(node1);
        Node node2 = skipList.find(16);
        System.out.println(node2);
        skipList.add(3);
        skipList.add(13);
        skipList.add(0);
        skipList.add(3);
        skipList.add(9);
        Node node3 = skipList.find(3);
        System.out.println(node3);
        Node node4 = skipList.find(0);
        System.out.println(node4);
        skipList.delete(3);
        Node node5 = skipList.find(3);
        System.out.println(node5);
        skipList.delete(2);
        Node node6 = skipList.find(2);
        System.out.println(node6);
    }

    public SkipList() {
        // topLevel = ThreadLocalRandom.current().nextInt(MAX_LEVEL);
        head = new Node[MAX_LEVEL];
        Node[] h = head;
        for (int i = 0; i < head.length; i++) {
            h[i] = new Node();
        }
    }

    // 查询
    public Node find(int value) {
        // int levelIndex = ThreadLocalRandom.current().nextInt(0, MAX_LEVEL);
        int levelIndex = topLevelIndex;
        Node[] tmp = head;
        for (int i = levelIndex; i >= 0; i--) {
            // p = tmp[i];
            while(tmp[i].next != null && tmp[i].next[i].data < value ) {
                tmp = tmp[i].next;
            }
            // tmp[i].next[i] == null || tmp[i].next[i].data >= value
            if(tmp[i].next != null && tmp[i].next[i].data == value) {
                return tmp[i].next[0];
            }
        }
        return null;
    }

    // 查询柱子
    public Node[] findColumn(int value) {
        // int levelIndex = ThreadLocalRandom.current().nextInt(0, MAX_LEVEL);
        int levelIndex = topLevelIndex;
        Node[] tmp = head;
        for (int i = levelIndex; i >= 0; i--) {
            // p = tmp[i];
            while(tmp[i].next != null && tmp[i].next[i].data < value ) {
                tmp = tmp[i].next;
            }
            // tmp[i].next[i] == null || tmp[i].next[i].data >= value
            if(tmp[i].next != null && tmp[i].next[i].data == value) {
                return tmp[i].next;
            }
        }
        return null;
    }

    // 增加
    public void add(int value) {
        if(find(value) != null) return;
        int levelIndex = ThreadLocalRandom.current().nextInt(0, MAX_LEVEL);
        if(levelIndex > topLevelIndex) {
            topLevelIndex = levelIndex;
        }
        // 先创建并初始化一个柱子
        Node[] insertArr = new Node[levelIndex + 1];
        for (int i = 0; i < insertArr.length; i++) {
            insertArr[i] = new Node(value);
        }
        Node[] tmp = head;
        // 遍历每一层
        for (int i = levelIndex; i >= 0; i--) {
            while(tmp[i].next != null && tmp[i].next[i].data < value){
                tmp = tmp[i].next;
            }
            insertArr[i].next = tmp[i].next;
            tmp[i].next = insertArr;
        }
    }

    // 删除
    public boolean delete(int value) {
//        Node[] column = findColumn(value);
//        if(column == null) return false;
        boolean exists = false;
        Node[] tmp = head;
        for (int i = topLevelIndex; i >= 0; i--) {
            while(tmp[i].next != null && tmp[i].next[i].data < value) {
                tmp = tmp[i].next;
            }
            if(tmp[i].next != null && tmp[i].next[i].data == value) {
                tmp[i].next = tmp[i].next[i].next;
                exists = true;
            }
        }
        return exists;
    }

    @NoArgsConstructor
    @Data
    private static class Node{
        private int data;
        private Node[] next;
        public Node(int data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    //", next=" + Arrays.toString(next) +
                    '}';
        }
    }
}
